package 中等.其他;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。
 * 今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。
 * 例如，如果未来7天股票的价格是 [100, 80, 60, 70, 60, 75, 85]，那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/online-stock-span
 */
public class 股票价格跨度_901 {

    public static void main(String[] args) {

    }

    /**
     * 模拟
     */
    class StockSpanner {

        private int[] record = new int[150001];

        private int idx = 0;

        public StockSpanner() {

        }

        public int next(int price) {
            record[idx] = price;
            idx++;

            int count = 0;
            for (int i = idx - 1; i >= 0; i--) {
                if (price >= record[i]) {
                    count++;
                } else {
                    break;
                }
            }

            return count;
        }
    }

    /**
     * 单调栈
     * 栈中存储索引和对应的价格
     * 每次 next 将栈顶 <= price 的元素弹出，最后和栈顶元素之差即为答案
     */
    class StockSpanner2 {

        private Deque<int[]> stack = new ArrayDeque<>();

        private int idx = 0;

        public StockSpanner2() {
            // 定义一个初始栈顶元素永远不会被弹出
            // 1 <= price <= 10^5
            stack.addFirst(new int[]{-1, 100001});
        }

        public int next(int price) {
            while (stack.peekFirst()[1] <= price) {
                stack.pollFirst();
            }

            int ans = idx - stack.peekFirst()[0];

            stack.addFirst(new int[]{idx, price});
            idx++;

            return ans;
        }
    }

}
